There are many scenarios where database records each have a defined validity interval. The validity interval may be defined by a start attribute and an end attribute for the interval. Some example of database records that may have defined validity intervals are car rental contracts with the corresponding rental period (pick up of the car until the car's return), insurance contracts with the corresponding validity period during which the insurance contract is in force, and materials having a minimal and maximum recommended load capacity. In some cases, the validity interval may not be fixed. For is example, the interval may be a day to several months.
It is often needed to be able to search database records to retrieve or identify the records whose validity interval satisfies a specified condition. For example, it may be needed to identify all records that have the interval covering one value, for example, the contracts that are valid on a particular date. Another example is that it may be needed to identify all records that have an overlap or some other kind of intersection with a search interval defined by a person performing a database search, for example, all contracts that are valid at least one day between February 1 and February 3.
In a typical case of database searching that involves such a condition, two inequality conditions may need to be used in a scan of an index to identify the records that satisfy the condition. For example, a first search may be to determine records that have a start date that is on or before February 3, and a second search would then be conducted to determine records that have an end date that is on or after February 1. In many databases, two inequality conditions cannot be included in the same scan the way equality conditions can be included in the same scan. As such, the first inequality condition would be used in a first scan of the entire index to identify all database records for which the first inequality condition is met. Then, the second inequality condition would be used in a second scan of only those records for which the first scan identified records. In many cases the same record will need to be scanned twice in order to be eliminated from consideration.
Database search performance—the time it takes for such a search to be conducted—may work with sufficient performance if the search is being conducted at one end of the entire range within which a valid interval may be defined. For example, if the validity range is a time period, and the range being searched for falls at the more recent end of the spectrum, the first inequality scan may identify only a very few records, and so the second inequality scan would only need to be run on a few records. On the other hand, where the validity period falls in the middle of the overall range, search performance may be degraded by multiple inequality scans being performed on the same record, where the second scan eliminates many records that the first scan could not eliminate.